import bean.TreeNode;

import java.util.HashMap;
import java.util.Map;

/**
 * @author 挚爱之夕
 * @version 1.0
 * @implSpec 中等
 * 给定两个整数数组 preorder 和 inorder ，
 * 其中 preorder 是二叉树的先序遍历，
 * inorder 是同一棵树的中序遍历，请构造二叉树并返回其根节点。
 * 输入: preorder = [3,9,20,15,7], inorder = [9,3,15,20,7]
 * 输出: [3,9,20,null,null,15,7]
 * @since 2023-09-17 20:35
 */
public class _105从前序与中序遍历序列构造二叉树 {
}

class Solution105 {
    private Map<Integer, Integer> indexMap;
    private int[] preorder, inorder;

    public TreeNode buildTree(int[] preorder, int[] inorder) {
        this.preorder = preorder;
        this.inorder = inorder;
        int n = preorder.length;
        // 构造哈希映射，帮助我们快速定位根节点
        indexMap = new HashMap<>();
        for (int i = 0; i < n; i++) {
            indexMap.put(inorder[i], i);
        }
        return build(0, n - 1, 0, n - 1);
    }

    private TreeNode build(int pre_left, int pre_right, int in_left, int in_right) {
        if (pre_left > pre_right) return null;
        //先序遍历第一个为根
        TreeNode root = new TreeNode(preorder[pre_left]);
        //得到root在中序遍历的位置
        int index = indexMap.get(preorder[pre_left]);
        //左子树节点数
        int leftLen = index - in_left;
        root.left = build(pre_left + 1, pre_left + leftLen, in_left, index - 1);
        root.right = build(pre_left + leftLen + 1, pre_right, index + 1, in_right);
        return root;
    }
}